#include<iostream>
#include<vector>
using namespace std;
struct Node
{
    int data;
    Node *next;
    Node(){
        data=0;
        next=nullptr;
    }
    Node(int x){
        data=x;
        next=nullptr;
    }
    Node(int x,Node* n){
        data=x;
        next=n;
    }
};


/**
 * 对一个链表，将第一个出现的元素保留，后面的元素的绝对值和前面的绝对值有相同的
 * 那么就去掉,这里题目要求保证时间复杂度最优，所以用空间换时间
 * 这里的元素范围是有界的，所以申请数组，利用直接映射hash确定当前元素是否被保存过
 */
void delete_same(Node* head,int n){
    Node* curr=new Node(0,head);
    vector<int> v(n+1,0);//用来保存下标i的元素是否存在
    while (curr->next!=nullptr)
    {
        int index=abs(curr->next->data);
        if(v[index]==0){//还没有被访问过，就标记为访问，往下走
            curr=curr->next;
            v[index]=1;
            continue;
        }else{//删除当前节点
            auto temp=curr->next;
            curr->next=curr->next->next;
            delete temp;
        }
    }
    return;
}

int main(void){
    Node*head =new Node(1,new Node(2,new Node(3,new Node(-1,new Node(-2,new Node(-3))))));
    delete_same(head,3);

    auto temp=head;
    while (temp!=nullptr)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }

    
    return 0;
}

/**
 * 时间复杂度为O(n)
 * 空间复杂度为O(1)
 */